#include <cstdio>
using namespace std;

const int max_amount = 50000;
const int max_coins = 100;

int main()
{
	int C[ max_coins + 1 ];

	int problem_count = 0;
	scanf( "%d", &problem_count );
	for( int i = 0; i < problem_count; i++ )
	{
		int count = 0;
		scanf( "%d", &count );

		if( count == 0 )
		{
			printf( "0\n" );
			continue;
		}
		
		int sum = 0;
		for( int j = 0; j < count; j++ )
		{
			scanf( "%d", &C[j] );
			sum += C[j];
		}

		bool F[ max_amount + 1 ] = {false};
		F[0] = true;
		F[C[0]] = true;

		int half = sum / 2;
		for( int u = 1; u < count; u++ )
		{
			int value = C[u];
			for( int v = half - value; v >= 0; v-- )
			{
				if( F[v] )
				{
					F[v + value] = true;
				}
			}
		}

		for( int u = half; u >= 0; u-- )
		{
			if( F[u] )
			{
				printf( "%d\n", (sum - u) - u );
				break;
			}
		}
	}

	return 0;
}
